package class06;

import utils.TreeNode;

import java.util.HashMap;

/**
 * @Description: Code05_根据先序中序遍历构建二叉树
 * @Author: WangWenpeng
 */
public class Code05_根据先序中序遍历构建二叉树 {
    public static TreeNode buildTree1(int[] pre, int[] mid) {
        if (pre == null || mid == null || pre.length != mid.length) {
            return null;
        }
        return f(pre, 0, pre.length - 1, mid, 0, mid.length - 1);
    }

    // 有一棵树，先序结果是pre[L1...R1]，中序结果是in[L2...R2]
    // 请建出整棵树返回头节点
    public static TreeNode f(int[] pre, int L1, int R1, int[] mid, int L2, int R2) {
        if (L1 > R1) {
            return null;
        }
        //先序遍历的第一个就是头节点
        TreeNode head = new TreeNode(pre[L1]);
        if (L1 == R1) {
            return head;
        }
        //在中序遍历中找到头节点的位置
        int find = L2;
        while (mid[find] != pre[L1]) {
            find++;
        }
        //递归调用
        head.left = f(pre, L1 + 1, L1 + find - L2, mid, L2, find - 1);
        head.right = f(pre, L1 + find - L2 + 1, R1, mid, find + 1, R2);
        return head;
    }

    //优化  空间换时间   将中序的放map中 直接拿，find不用遍历了
    public static TreeNode buildTree2(int[] pre, int[] mid) {
        if (pre == null || mid == null || pre.length != mid.length) {
            return null;
        }
        HashMap<Integer, Integer> valueIndexMap = new HashMap<>();
        for (int i = 0; i < mid.length; i++) {
            valueIndexMap.put(mid[i], i);
        }
        return g(pre, 0, pre.length - 1, mid, 0, mid.length - 1, valueIndexMap);
    }

    // 有一棵树，先序结果是pre[L1...R1]，中序结果是in[L2...R2]
    // 请建出整棵树返回头节点
    public static TreeNode g(int[] pre, int L1, int R1, int[] mid, int L2, int R2,
                             HashMap<Integer, Integer> valueIndexMap) {
        if (L1 > R1) {
            return null;
        }
        TreeNode head = new TreeNode(pre[L1]);
        if (L1 == R1) {
            return head;
        }
        int find = valueIndexMap.get(pre[L1]);
        head.left = g(pre, L1 + 1, L1 + find - L2, mid, L2, find - 1, valueIndexMap);
        head.right = g(pre, L1 + find - L2 + 1, R1, mid, find + 1, R2, valueIndexMap);
        return head;
    }
}
